object heap {
    def max_heapify(A: Array[Int], i: Int, heapsize: Int){
    	
	var l = 0;
	var r = 0;
	var largest = 0;

	if(l <= heapsize && A(l) > A(i)){
	     largest = l;
	} else {
	     largest = i;
	}
	if( r <= heapsize && A(r) > A(l)){
	    largest = r;
	}
	if(largest != i){
		   var temp = 0;
		   temp = A(i);
		   A(largest) = A(i);
		   A(i) = temp
		   max_heapify(A, largest, heapsize);
	}
    }

    def build_max_heap(A: Array[Int]){
    	var heapsize = A.length;
	for( i <- heapsize / 2 to 1 by -1){
	     max_heapify(A, 1, heapsize);
	}
	
    }
    def main(args: Array[String]) {
      var N = 11;
      var A = new Array[Int](N);
      A(0) = Int.MaxValue;
      A(1) = 16;
      A(2) = 4;
      A(3) = 10;
      A(4) = 14;
      A(5) = 7;
      A(6) = 9;
      A(7) = 3;
      A(8) = 2;
      A(9) = 8;
      A(10) = 1;
      build_max_heap(A);
      for(i <- 1 until A.length-1){
      	    println(A(i));
	    } 
    }
  }